package dfs;

public class 黄金矿工 {
    public static void main(String[] args) {
        int[][] grid = {{0,6,0},{5,8,7},{0,9,0}};
        int maximumGold = getMaximumGold(grid);
        System.out.println(maximumGold);
    }
    static public int getMaximumGold(int[][] grid) {
        int sum=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]==0)
                    continue;
                sum=Math.max(sum,bfs(grid,i,j));
            }
        }
        return sum;
    }

    private static int bfs(int[][] grid, int i, int j) {
        //边界条件
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j]==0)
            return 0;
        int temp=grid[i][j];
        grid[i][j]=0;
        int up = bfs(grid, i - 1, j);  //向上
        int down=bfs(grid,i+1,j); //向下
        int left=bfs(grid,i,j-1); //向左
        int right=bfs(grid,i,j+1);  //向右
        //找到最大值
        int max=Math.max(Math.max(up,down),Math.max(left,right));
        grid[i][j]=temp;
        return grid[i][j]+max;
    }
}
